"""
小孩爬楼梯，一次可以爬1个台阶，2个台阶，3个台阶，
问走完10个台阶，一共有多少种走法
"""
import functools


# n! = n * (n-1)!
def fac(num):
    if num == 0:
        return 1
    return num * fac(num - 1)


@functools.lru_cache()
def fib(num):
    if num in (1, 2):
        return 1
    return fib(num - 1) + fib(num - 2)


for n in range(1, 121):
    print(n, fib(n))
